/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-06-27
 * Time: 22:26
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        // 先找到这个节点
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null && cur.val != key) {
            prev = cur;
            if (cur.val > key) {
                cur = cur.left;
            }else {
                cur = cur.right;
            }
        }
        if (cur == null) {
            // 没找到
            return root;
        }
        // 找到了
        if (cur.left == null && cur.right == null) {
            // 叶子节点
            if (prev == null) {
                return null;
            }else {
                if (cur == prev.left) {
                    prev.left = null;
                }else {
                    prev.right = null;
                }
            }
        } else if (cur.left == null) {
            // 左子树为空
            if (prev == null) {
                return root.right;
            }
            if (prev.left == cur) {
                prev.left = cur.right;
            }else {
                prev.right = cur.right;
            }
        }else if (cur.right == null) {
            // 右子树为空
            if (prev == null) {
                return root.left;
            }
            if (prev.left == cur) {
                prev.left = cur.left;
            }else {
                prev.right = cur.left;
            }
        }else {
            // 左右子树均不为空
            prev = cur;
            TreeNode replace = cur.right;
            // 找右子树中的最小值
            while (replace.left != null) {
                prev = replace;
                replace = replace.left;
            }
            // cur 中的值替换为 替罪羊中的值
            cur.val = replace.val;
            // 不能直接把这个节点删除了, 因为他的右子树中可能还有节点
            if (replace == prev.left) {
                prev.left = replace.right;
            }else {
                prev.right = replace.right;
            }
        }
        return root;
    }
}